題目連結: Invert Binary Tree

題目描述為給定一個二元樹，將其反轉。

思路 1: 遞迴法

我們可以按照定義將該節點的 left,right 反轉後，再繼續將左右節點的 left,right 反轉，直到遍歷所有節點。

• 複雜度評估
  設給定二元樹的節點數量為 N。我們需要遍歷全部節點一次，時間複雜度為 O(N)。此方法只用了常數個變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func invertTree(root *TreeNode) *TreeNode {
    
    if root == nil {
        return nil
    }
    
    root.Left, root.Right = root.Right, root.Left
    
   invertTree(root.Left)
   invertTree(root.Right)
    
    return root
}

小結:

關於二元樹的各種遍歷，我們在day19-Same Tree已經有提過。
Homebrew的作者 Max Howell 曾經在 Google 面試時因為沒完成此題而被拒絕，引發諸多討論。
Max Howell 本人的回應在此。

我將解法上傳程式碼到此，因此題需要實作 TreeNode，我尚未加上測試過程。